package me.algo.lst;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Optional;
import java.util.TreeMap;

/**
 * @author guozheng
 * @date 2024/5/12
 */
public class L9 {

    public static void main(String[] args) {
//        ListNode node = new ListNode(2, new ListNode(1));
        ListNode node = new ListNode(1, new ListNode(2, new ListNode(3)));

//        ListNode node = new ListNode(1, new ListNode(7, new ListNode(5, new ListNode(1, new ListNode(9, new ListNode(2, new ListNode(5, new ListNode(1))))))));
        int[] ints = nextLargerNodes(node);

        System.out.println(ints);
    }
    public static int[] nextLargerNodes(ListNode head) {

        TreeMap<Integer, Integer> mounts = new TreeMap<>();
        int len = 0;
        ListNode cur = head;
        int max = 0;
        int up = 0;
        int last = -1;
        while (cur != null) {
            if (cur.val > max && cur.val > last && len != 0) {
                max = cur.val;
                up = 1;
                last = cur.val;
                len++;
                cur = cur.next;
                continue;
            }

            if (up == 1) {
                mounts.put(len - 1, max);
                max = 0;
                mounts.put(len, max);
                if (!(cur.val > last)) {
                    up = 0;
                }
            }
            last = cur.val;
            len++;
            cur = cur.next;

        }
        if (!mounts.containsKey(len) && up == 1) {
            mounts.put(len - 1, max);
            mounts.put(len, 0);
        }
        Iterator<Map.Entry<Integer, Integer>> iterator = mounts.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> ele = iterator.next();
            Integer key = ele.getKey();
            Integer value = ele.getValue();
            Map.Entry<Integer, Integer> entry = mounts.ceilingEntry(key + 2);

            if (value != null && entry != null && entry.getValue() > value) {
                Integer val = entry.getValue();
                int nxt0 = key + 1;
                if (mounts.containsKey(nxt0)) {
                    mounts.put(nxt0, val);
                }
            }

        }
        int[] rtn = new int[len];
        for (int i = 0; i < len; i++) {
            Map.Entry<Integer, Integer> ceilingEntry = mounts.ceilingEntry(i+1);
            if (ceilingEntry == null) {
                continue;
            }
            Integer key = ceilingEntry.getKey();
            if (i <= key) {
                Integer value = ceilingEntry.getValue();
                rtn[i] = value;
            }
        }


        return rtn;
    }

}
